package tree;

/**
 * description:
 * author:张腾
 * date:2021-04-09
 */

/**
 * 红黑树 底层是二叉排序树
 * 为了维持树的平衡
 * 特性：  1.节点是红色或黑色。
 *        2.根节点是黑色。
 *        3.每个叶子节点都是黑色的空节点（NIL节点）。
 *        4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
 *        5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
 * @param <Key>
 * @param <Value>
 */
public class RedBlackTree<Key extends Comparable<Key> ,Value> {

    public static void main(String[] args) {
        RedBlackTree<Integer, String> tree = new RedBlackTree<>();
        tree.put(1,"1");
        tree.put(2,"2");
        tree.put(3,"3");
        System.out.print(tree.get(1)+" "+tree.get(2)+" "+tree.get(3));
    }
    //根节点
    private Node root;
    //树中元素的个数
    private int N;

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node{
        public Key key;  //键
        public Value value;  //值
        public Node        left;  //左子树
        public Node right;  //右子树
        public boolean color;  //父节点指向它的链接的颜色 true即为红色，false为黑色

        public Node(Key key, Value value, Node left, Node right, boolean color) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.color = color;
        }
    }

    public int size(){
        return N;
    }

    //判断当前节点的父指向链接是否为红色
    private boolean isRed(Node x){
        if (x==null){
            return false;
        }

        return x.color==RED;
    }

    //左旋
    private Node rotateLeft(Node h){
        //获取h节点的右子节点，表示为x
        Node x = h.right;
        //让x节点的左子节点成为h节点的右子节点
        h.right = x.left;
        //让h成为x节点的左子节点
        x.left = h;
        //让x节点的color属性等于h节点的color属性
        x.color = h.color;
        //让h节点的color属性变为红色
        h.color = RED;

        return x;
    }

    //右旋
    private Node rotateRight(Node h){
        //获取h节点的左子节点，表示为x
        Node x = h.left;
        //让x的右子节点成为h节点的左子节点
        h.left = x.right;
        //让h成为x的右子节点
        x.right = h;
        //让x的color属性等于h的color
        x.color = h.color;
        //让h的color属性为红色
        h.color = RED;

        return x;
    }

    //颜色反转
    private void flipColor(Node h){
        //当前节点变为红色，两个子节点变为黑色
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    //在整个树上完成插入操作
    public void put(Key key,Value value){
        root = put(root,key,value);
        //根节点的颜色总是黑色
        root.color = BLACK;
    }

    //在指定树中，完成插入操作，并返回添加元素后的新的树
    public Node put(Node h,Key key,Value value){
        //判断h是否为空，若是则直接返回一个红色节点
        if (h==null){
            N++;
            return new Node(key,value,null,null,RED);
        }

        //比较h节点的键和key的大小
        int cmp = key.compareTo(h.key);
        if (cmp>0){
            h.right = put(h.right,key,value);
        }else if (cmp<0){
            h.left = put(h.left,key,value);
        }else{
            h.value = value;
        }

        //进行左旋：当当前节点的右子节点为红色，左子节点为黑色
        if (isRed(h.right) && !isRed(h.left)){
            h = rotateLeft(h);
        }
        //进行右旋：当当前节点的左子节点为红色，左子节点的左子节点也为红色
        if (isRed(h.left) && isRed(h.left.left)){
            h = rotateRight(h);
        }
        //颜色反转：当当前节点的左子节点和右子节点都为红色
        if (isRed(h.left) && isRed(h.right)){
            flipColor(h);
        }

        return h;
    }

    public Value get(Key key){
        return get(root,key);
    }

    //从指定树x中获取key对应的值
    public Value get(Node x, Key key){
        if (x==null){
            return null;
        }

        int cmp = key.compareTo(x.key);

        if (cmp>0){
            return get(x.right,key);
        }else if (cmp<0){
            return get(x.left,key);
        }else{
            return x.value;
        }
    }

}

